/**
 * https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/
 * 二叉树中的众数
 * @param root 
 */
const findMode = (root: TreeNode | null): number[] => {
    // 树为空
    if (root == null) return []


    const ans: number[] = []
    const inOrder = (p: TreeNode | null) => {
        if (p === null) return;

        /**
         * 获取前驱节点
         * @param n 
         */
        const getAced = (n: TreeNode) => {
            let left = n.left;
            while (left !== null && left.right !== null && left.right !== n) {
                left = left.right;
            }
            return left;
        }

        while (p !== null) {
            if (p.left !== null) {
                // 获取前驱节点
                const aced = getAced(p)!;
                if (aced.right === null) {
                    aced.right = p
                    p = p.left
                } else {
                    // 访问节点p
                    update(p.val)
                    aced.right = null;
                    // 指向右边
                    p = p.right;
                }
            } else {
                // 访问节点, 指向右孩子
                update(p.val)
                p = p.right;
            }
        }




    }

    let prevVal = Number.MIN_SAFE_INTEGER,
        curCount = 0,
        maxCount = 0;
    // 对数组进行筛选
    const update = (val: number) => {
        console.log(val)
        if (prevVal === val) {
            // 相等
            curCount++;
        } else {
            // 复位
            curCount = 1;
            prevVal = val
        }

        if (curCount > maxCount) {
            // 清空数组
            ans.length = 0;
            ans.push(prevVal)
            maxCount = curCount
        } else if (curCount === maxCount) {
            // 放入数组中
            ans.push(prevVal)
        }

    }

    inOrder(root)

    return ans
}


const findMode3 = (root: TreeNode | null): number[] => {
    // 树为空
    if (root == null) return []


    const ans: number[] = []
    const vs: number[] = []
    const inOrder = (n: TreeNode | null) => {
        if (n === null) return;
        inOrder(n.left)
        update(n.val)
        inOrder(n.right)
    }

    let prevVal = Number.MIN_SAFE_INTEGER,
        curCount = 0,
        maxCount = 0;
    // 对数组进行筛选
    const update = (val: number) => {
        if (prevVal === val) {
            // 相等
            curCount++;
        } else {
            // 复位
            curCount = 1;
            prevVal = val
        }

        if (curCount > maxCount) {
            // 清空数组
            ans.length = 0;
            ans.push(prevVal)
            maxCount = curCount
        } else if (curCount === maxCount) {
            // 放入数组中
            ans.push(prevVal)
        }

    }


    inOrder(root)
    return ans
}




const findMode2 = (root: TreeNode | null): number[] => {
    // 树为空
    if (root == null) return []

    // 模拟队列
    const queue: TreeNode[] = []
    // 将根放入队列中
    queue.push(root);

    const map: Record<number, number> = {};
    const ans: number[] = []

    while (queue.length > 0) {
        const n = queue.shift()!
        // 没有默认为0
        map[n.val] = map[n.val] ? map[n.val]++ : 0
        // 左子树不为空
        if (n.left !== null) queue.push(n.left)
        // 右子树不为空
        if (n.right !== null) queue.push(n.right);
    }

    // 计算数量
    const keyAvals = Object.entries(map);

    // 从大到小排序
    keyAvals.sort((a, b) => b[1] - a[1])

    const len = keyAvals.length;
    // 最大值
    const max = keyAvals[0][1]
    ans.push(+keyAvals[0][0])
    for (let i = 1; i < len; i++) {
        // 大于等于最大值, 满足条件
        if (keyAvals[i][1] >= max) ans.push(+keyAvals[i][0])
        else break;
    }

    return ans
};